This invention relates to the transmission of data over communications networks including wide area networks. More specifically, this invention relates to methods and apparatus for scheduling data packets for transmission over a data link. The scheduling methods and apparatus may be used in systems for providing a plurality of differentiated services each providing a different level of Quality of Service (xe2x80x9cQoSxe2x80x9d) over wide area networks. The scheduling methods and apparatus have particular application in Internet Protocol (xe2x80x9cIPxe2x80x9d) networks.
Maintaining efficient flow of information over data communication networks is becoming increasingly important in today""s economy. Telecommunications networks are evolving toward a connectionless model from a model whereby the networks provide end-to-end connections between specific points. In a network which establishes specific end-to-end connections to service the needs of individual applications the individual connections can be tailored to provide a desired bandwidth for communications between the end points of the connections. This is not possible in a connectionless network. The connectionless model is desirable because it saves the overhead implicit in setting up connections between pairs of endpoints and also provides opportunities for making more efficient use of the network infrastructure through statistical gains. Many networks today provide connectionless routing of data packets, such as Internet Protocol (xe2x80x9cIPxe2x80x9d) data packets over a network which includes end-to-end connections for carrying data packets between certain parts of the network. The end-to-end connections may be provided by technologies such as Asynchronous Transfer Mode (xe2x80x9cATMxe2x80x9d), Time Division Multiplexing (xe2x80x9cTDMxe2x80x9d) and SONET/SDH.
A Wide Area Network (xe2x80x9cWANxe2x80x9d) is an example of a network in which the methods of the invention may be applied. WANs are used to provide interconnections capable of carrying many different types of data between geographically separated nodes. For example, the same WAN may be used to transmit video images, voice conversations, e-mail messages, data to and from database servers, and so on. Some of these services place different requirements on the WAN.
For example, transmitting a video signal for a video conference requires fairly large bandwidth, short delay (or xe2x80x9clatencyxe2x80x9d), small delay jitter, and reasonably small data loss ratio. On the other hand, transmitting e-mail messages or application data can generally be done with lower bandwidth but can tolerate no data loss. Further, it is not usually critical that e-mail be delivered instantly. E-mail services can usually tolerate longer latencies and lower bandwidth than other services.
A typical WAN comprises a shared network which is connected by access links to two or more geographically separated customer premises. Each of the customer premises may include one or more devices connected to the network. More typically each customer premise has a number of computers connected to a local area network (xe2x80x9cLANxe2x80x9d). The LAN is connected to the WAN access link at a service point. The service point is generally at a xe2x80x9cdemarcationxe2x80x9d unit or xe2x80x9cinterface devicexe2x80x9d which collects data packets from the LAN which are destined for transmission over the WAN and sends those packets across the access link. The demarcation unit also receives data packets coming from the WAN across the access link and forwards those data packets to destinations on the LAN.
Currently an enterprise which wishes to link its operations by a WAN obtains an unallocated pool of bandwidth for use in carrying data over the WAN. While it is possible to vary the amount of bandwidth available in the pool (by purchasing more bandwidth on an as-needed basis), there is no control over how much of the available bandwidth is taken by each application.
As noted above, guaranteeing the Quality of Service (xe2x80x9cQoSxe2x80x9d) needed by applications which require low latency is typically done by dedicating end-to-end connection-oriented links to each application. This tends to result in an inefficient allocation of bandwidth. Network resources which are committed to a specific link are not readily shared, even if there are times when the link is not using all of the resources which have been allocated to it. Thus committing resources to specific end-to-end links reduces or eliminates the ability to achieve statistical gains. Statistical gains arise from the fact that it is very unlikely that every application on a network will be generating a maximum amount of network traffic at the same time.
If applications are not provided with dedicated end-to-end connections but share bandwidth then each application can, in theory, share equally in the available bandwidth. In practice, however, the amount of bandwidth available to each application depends on things such as router configuration, the location(s) where data for each application enters the network, the speeds at which the application can generate the data that it wishes to transmit on the network and so on. The result is that bandwidth may be allocated in a manner that bears no relationship to the requirements of individual applications or to the relative importance of the applications. There are similar inequities in the latencies in the delivery of data packets over the network.
The term Quality of Service is used in various different ways by different authors. In general, QoS refers to a set of parameters which describe the required traffic characteristics of a data connection. In this specification the term QoS refers to a set of one or more of the following interrelated parameters which describe the way that a data connection treats data packets generated by an application:
Minimum Bandwidthxe2x80x94a minimum rate at which a data connection must be capable of forwarding data originating from the application. The data connection might be incapable of forwarding data at a rate faster than the minimum bandwidth but should always be capable of forwarding data at a rate equal to the rate specified by the minimum bandwidth;
Maximum Delayxe2x80x94a maximum time taken for data from an application to completely traverse the data connection. QoS requirements are met only if data packets traverse the data connection in a time equal to or shorter than the maximum delay;
Maximum Lossxe2x80x94a maximum fraction of data packets from the application which may not be successfully transmitted across the data connection; and,
Jitterxe2x80x94a measure of how much variation there is in the delay experienced by different packets from the application being transmitted across the data connection. In an ideal case, where all packets take exactly the same amount of time to traverse the data connection, the jitter is zero. Jitter may be defined, for example, as any one of various statistical measures of the width of a distribution function which expresses the probability that a packet will experience a particular delay in traversing the data connection.
Different applications require different levels of QoS.
Recent developments in core switches for WANs have made it possible to construct WANs capable of quickly and efficiently transmitting vast amounts of data. There is a need for a way to provide network users with control over the QoS provided to different data services which may be provided over the same network.
Service providers who provide access to WANs wish to provide their customers with Service Level Agreements rather than raw bandwidth. This will permit the service providers to take advantage of statistical gain to more efficiently use the network infrastructure while maintaining levels of QoS that customers require. To do this, the service providers need a way to manage and track usage of these different services. There is a particular need for relatively inexpensive apparatus and methods for facilitating the provision of services which take advantage of different levels of QoS.
Applications connected to a network generate packets of data for transmission on the network. In providing different levels of service it is necessary to be able to sort or xe2x80x9cclassifyxe2x80x9d data packets from one or more applications into different classes which will be accorded different levels of service. The data packets can then be transmitted in a way which maintains the required QoS for each application. Data packets generated by one or more applications may belong to the same class.
There are many known methods for scheduling the transmission of packets over a data link. These include simple round robin schemes, Class-Based Queuing (CBQ), Worst Case Weighted Fair Queuing (WF2Q) and Worst Case Weighted Fair Queuing+(WF2Q+). All of these methods have disadvantages. CBQ, WF2Q and WF2Q+ all introduce undesirably long queuing delays. A problem with many of these scheduling protocols is that they introduce too much delay into the transmission of those packets which must be delivered with minimum latency.
There is a need for a fast scheduling method and apparatus which can transmit xe2x80x9creal timexe2x80x9d packets with very small delays but which can also schedule the transmission of non-real time packets fairly.
This invention provides methods and apparatus for scheduling the forwarding of data packets over a data link. The methods of the invention involve receiving classified data packets. In one embodiment of the invention, the methods include selecting one of a plurality of data packets by selecting an eligible group of data packets and determining whether data packets in the eligible group all belong to classes having the same priority or belong to classes having different priorities. If the data packets in the eligible group belong to two or more classes having different priorities the method selects one data packet by applying a selection criterion to an eligible sub-group containing those one or more data packets in the eligible group which belong to classes having a highest priority. If the data packets in the eligible group all belong to classes having the same priority, the method selects one data packet by applying a selection criterion to all data packets in the eligible group. The method provides reduced queuing delays for packets belonging to higher priority classes.
In preferred embodiments the selection criterion comprises a first to finish selection criterion. The method preferably includes maintaining a virtual time value. Selecting the eligible group preferably comprises selecting packets having a start time less than or equal to the virtual time value.
The invention may be practised with a plurality of scheduling engines interlinked to form a hierarchical tree, the tree including at least a parent scheduling engine and a plurality of child scheduling engines linked to the parent scheduling engine. The parent scheduling engine selects one data packet from the data packets being held by the child scheduling engines. In some embodiments, whenever a data packet belonging to a high priority class becomes available for selection by a child scheduling engine and a data packet already selected and being held by that child scheduling engine belongs to a lower priority class, the data packet belonging to the high priority class is made available for selection by the parent scheduling engine in place of the already selected data packet.
The invention also provides apparatus for scheduling transmission of data packets on a data link, the apparatus comprises:
a) a memory capable of holding a plurality of data packets queued in a plurality of queues;
b) means for keeping a start time, a finish time and a priority for a packet at a head of each of the queues;
c) a scheduling engine adapted to select one packet from a plurality of packets at the heads of the queues, the scheduling engine comprising:
i) a counter for maintaining a virtual time for the scheduling engine;
ii) means for comparing the start time for each packet to the virtual time for the scheduling engine to select an eligible group of packets;
iii) means for comparing the priorities of packets in the eligible group of packets and eliminating from the eligible group packets having a priority lower than a priority for another packet in the eligible group; and,
iv) means for selecting one packet from the eligible group having an earliest finish time.
Other aspects and features of the invention are described below.